//https://leetcode.cn/problems/combination-sum-iii/submissions/525570558/?envType=daily-question&envId=2024-04-21


class Solution 
{
public:
    using IntList = std::vector<int>;
    using IntList2 = std::vector<IntList>;

    void Dfs(int k, int n, IntList2& res, IntList& int_list, int cur_num)
    {
        if(k == 0 && n==0)
        {
            res.emplace_back(int_list);
            return;
        }

        if(k==0)return;

        for(int i = cur_num; i<10 && n>=i; ++i)
        {
            int_list.emplace_back(i);
            Dfs(k-1, n-i, res, int_list, i+1);
            int_list.pop_back();
        }
    }

    IntList2 combinationSum3(int k, int n) 
    {
        IntList2 res;
        IntList int_list;
        Dfs(k, n, res, int_list,1);
        return res;
    }
};